Peer-to-peer (P2P) networks have become increasingly popular with their primary application being file-sharing. Others are using P2P networks for communication, such as Skype®, which has implemented a voice over Internet protocol (VoIP) P2P telephone service.
Distributed hash tables (DHTs) are used in certain P2P networks to improve the efficiency of locating resources on these networks. In these P2P networks, a hash key (resource ID) is associated with a resource (e.g., a file) and each node in the system is responsible for storing a certain range of hash keys of a hash space. A lookup operation looking for a particular key is routed through the P2P network to the node responsible for the key using a specific routing algorithm. Node identifiers (node ID s) are assigned to each node in the P2P network and are mapped to the same hash space as the resource IDs. That is, each node is responsible for storing all resources that have a certain range of resource IDs. Typically, in a DHT resources are assigned to a node having a node identifier (node ID) that is closest, according to some location determination, to the resource ID. Details of the methods used to determine the location of the identifiers depend on the particular DHT mechanism being used. Nodes may exchange messages in response to a node joining or leaving to maintain the DHTs.
An exemplary Distributed Hash Table (DHT) is defined in an article by I. Stoica et al. entitled, “Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications,” in ACM SIGCOMM'01, August 2001. A large scale Chord network may be built using a huge hash key space, such as a set of 128 bit integers and a cryptographic hash function such as the SHA-1 function, defined in a standard entitled “Secure Hash Standard,” NIST, FIPS PUB 180-1, April 1995.
FIGS. 1A and 1B are schematic diagrams of a conventional network using a Chord topology. FIG. 1A illustrates a DHT for the conventional network prior to network resource 5 joining and FIG. 1B illustrates the updating of the DHT for the conventional network as network resource 5 joins the conventional network.
Referring now to FIG. 1A, an exemplary Chord P2P network 100 includes nodes with node IDs 0-15 (hereafter referred to as nodes 0-15) and resources (not shown) assigned identifiers from an identifier space. Network 100 may include a physical network 110, a plurality of physical nodes, 120, 125, 130, 135 and 140, a plurality of processors 150, 155, 160, 165 and 170 which communicate with each other via physical nodes 120, 125, 130, 135 and 140, respectively. Physical network 110 may include any number of physical nodes and corresponding processors. Each processor 150, 155, 160, 165 and 170 may include a finger table that forms a portion of a DHT 180.
In the example illustrated, the number of bits assigned to each identifier is 4 and, thus, the identifier space is 0-15. The number of bits, however, may be any number and may be denoted as m. Thus, the identifier space may consist of numbers from 0 to 2m−1. Modulo 2m is used for numeric operations and, thus, the identifier space may be ordered in a circular fashion, forming an identifier circle, called a Chord ring. A resource ID is a hash key generated from the name of the resource. As described above, it may be desirable to use a cryptographic hash function such as SHA-1.
A resource with key k may be assigned to the first node having a node ID that is equal to or that follows k in Chord ring 100. Such a node is called the successor of key k, denoted by successor(k). Successor(k) is the first node clockwise from k in the Chord ring 100. Predecessor(k) is the first node counter-clockwise from k in the Chord ring 100. With respect to a particular node, for example, node 2, the next node in Chord ring 100 (e.g., as illustrated by the node which is the next in a clockwise orientation) is called its successor (i.e., node 9) and the previous node (the node counter clockwise) in the Chord ring 100 is its predecessor (i.e., node 0).
Each node is linked to (e.g., tracks), in a finger table, m other nodes called fingers that are the successors of keys n+2i-1 for each i=1, . . . , m. For any particular node, the nodes identified in its finger table are neighboring nodes, since these nodes are reachable in one hop. Further, a particular node may keep track of its predecessor node. Each node has many entries pointing to nearby nodes, and fewer entries pointing to more remote nodes. These finger tables are populated when a respective node joins the Chord ring 100, and are maintained via communication among various nodes during the operation of Chord ring 100.
A resource with resource ID k is stored by successor(k). As nodes join or leave, resources may be stored on different nodes. Thus, information related to nodes is exchanged as nodes join and leave the network. If a node failure occurs, redundant information maintained in successor and predecessor nodes of the first node may be used to maintain Chord ring 100.
Communications may be routed based on a characteristic of the finger tables, namely that nodes have more information about nodes (node IDs) closer to their identifier space than those further away. When locating a resource with a particular resource ID, for example, a lookup operation may be used. The node initiating the operation (e.g., a first node) may forward a query to a node from its finger table (e.g., a second node) that is either successor(resource ID) or a node with the largest node ID that is smaller (modulo 2m) than k. This process may be repeated, if necessary, from node to node until successor(k) is reached. That is, the second node may forward the query to another node (a third node) based on the finger table of the second node and this process may be repeated until successor(k) is reached. A finger of node n is successor(k) if the finger is the successor of n+2i-1 for such that key k is equal to or greater than n+2i-1 and the finger's node ID is equal to or greater than key k. That is, if, for a certain i=1, . . . , m, n+2i-1≦k≦successor (n+2i-1), then successor(n+2i-1) is also successor(k). During the forwarding steps, the query may reach predecessor(k). The successor of predecessor(k) is successor(k), and thus predecessor(k) forwards the query to successor(k). A node knows if it is successor(k) if its predecessor's node ID is smaller than key k (modulo 2m). Upon receiving the query, successor(k) replies to the query originator (the first node) with the requested information corresponding to the key if it has the information requested in the query. Otherwise, successor(k) replies to the query originator with a lookup failure message. In a Chord ring that has N nodes, the query reaches successor(k), on average, in log(N) hops. That is, if the Chord ring has 64,000 nodes, any query for resource k, on average, takes 16 hops to reach successor(k). This characteristic is the same for many known DHTs such as Chord, Pastry, and Tapestry.
Typical query messages contain the target resource name or identifier and a Time-to-Live (TTL) value. Intermediate nodes forwarding the query messages may decrement the TTL value.
To facilitate proper operation of the Chord ring 100, each node maintains its finger table and as a node joins or leaves the network 100, Chord finger tables throughout the Chord ring 100 are automatically updated accordingly.
In the exemplary system, when a joining node requests to join the network, the joining node applies the hash function of the DHT, for example, to the IP address of the joining node to generate a node ID.
Each finger table may include a resource ID field 185 and a node ID field 190, among others. Each finger table may further include, for example, finger table entries 180-1, 180-2, 180-3 and 180-4. It is understood by one of skill in the art that based on conventional chord methodologies as disclosed above, the entries in each finger table are as shown in FIG. 1A for a Chord ring having nodes 0-15 and processors associated with (joined at) nodes 0, 2, 9, 12 and 15.
As illustrated in FIG. 1B, when node 5 (i.e., the node with node ID 5) joins network 100, it sends a join message to its successor node (i.e., node 9) that it is joining network 100. Node 9 in a reply message includes information relating to its predecessor (i.e., node 2 in this example). Node 5 then looks up its other fingers. Node 5's fingers are successor (5+2i-1) for each i=1, . . . , m. In FIG. 1B, node 5's fingers are successor(6), successor(8), successor(9) and successor(14). Because there is no other node between node 5 and node 9, node 5 recognizes that node 9 is successor(6), successor(8) and successor(9). Because node 5 does not know successor(14) yet, node 5 may send a query (not shown) with target resource ID 14. The query may be forwarded to successor(14) as described above. Upon receiving the query, node 15 that is successor(14) may send a reply to node 5. Node 5 then may insert a pointer to node 15 as successor(14) in its finger table. For a Chord network of N nodes, a node may have, on average, log(N) different fingers. A lookup message for each unique finger may take about log(N) hops to forward. Thus, in the process of filling a finger table for a joining node, messages may be propagated in the P2P network and the number of hops to complete this process may be on the order of log2(N).
After filling its finger table, the joining node may desirably notify other nodes for which it is a new finger and their finger tables may be updated. In general, for the joining node n and its predecessor p, the arrival notification message desirably may be sent to the nodes whose node ID is r such that p−2i-1<r≦n−2i-1 for i=1, . . . , m, such that node n sends an arrival notification message toward successor (p−2i-1) for i=1, . . . , m. The arrival notification message may be forwarded in the same way as a query for resource (p−2i-1) is forwarded. Upon receiving the arrival notification message, successor(p−2i-1) may update its finger table accordingly and may forward the arrival notification message to its successor if the successor's node ID is equal to or smaller than n−2−1. In FIG. 1B, node 12, 15, 0, and 2 update their finger tables to reflect that node 5 joined the network. The communications of the arrival notification messages are denoted by the solid arrows from node 5 to nodes 12, 15, 0 and 2. Each arrival notification message is forwarded, on average, for log(N) hops until it reaches its destination in a similar manner to a query message. Finger table updates include: (1) node 12 updating its last finger table entry 180-4 to (4:5) to associate resource ID 4 with node 5; (2) node 15 updating its third finger table entry 180-3 to (3:5) to associate resource ID 3 with node 5; (3) node 0 updating its third finger table entry 180-3 to (4:5) to associate resource ID 4 with node 5 and (4) node 2 updating its first two finger table entries 180-1 and 180-2 to (3:5) and (4:5), respectively, to associate resource IDs 3 and 4 with node 5. In this way, all finger tables in P2P network 100 may be updated to reflect node 5 joining P2P network 100.
It is appreciated by one of skill in the art that when a new node joins a Chord network, significant traffic is generated to fill the finger table of the joining node and to update the finger tables of the nodes for which the joining node is a new finger. Further, when a node leaves the Chord network, the finger tables of the nodes that point to the leaving node may be updated. Updating these finger tables uses a similar procedure to that described above and also generates significant traffic on the Chord network.
Many known DHTs, for example, those used in other P2P networks, have the same characteristic that significant traffic is generated to maintain the DHT when a node joins or leaves the P2P network.